Computer systems comprise a main memory, one or more bulk memories e.g., disk memories, a processor, and input-output devices.
In the case of personal computers, there is a very large installed base of computers in which the main memory has a limited maximum capacity e.g., 640 kilobytes or 1 megabyte of random access memory. Computers with these limited ranges of main memory capacity have a continuing substantial share of the current market in personal computers. In the case of larger multi-tasking computers, there is continuing competition among application programs for main memory capacity.
Software for a computer comprises an "operating system" and application programs e.g., word processing programs, spread sheet programs, etc. The operating system software manages the system hardware and executes code presented by an application program. It is the responsibility of the application software to manage the allocation of its available main memory space during an execution session.
Although many application programs perform quite well in computers with limited available main memory, there is a demand in the market place for application programs which operate faster and process larger volumes of data within the hardware constraints. These are competing requirements. When the volume of code of an application and/or the volume of data actively processed by the code approaches or reaches the available main memory capacity, code execution is slowed; and in some cases, if the demand for main memory exceeds the available capacity, processing may be halted or data lost.
As a solution to limited main memory capacity, some application programs provide software mechanisms for "swapping" overlay code and data objects between main memory and bulk memory. Objects, code or data, are sections of code or data which are contiguous and ordered within the memory space assigned to the object; however, objects may have arbitrary memory locations relative to each other. Objects which are in main memory are termed "resident", and objects which are in bulk memory and not in main memory are termed "suspended" or non-resident. Only objects which are resident can be executed or directly accessed. If a program in progress needs to execute a suspended code object or access a suspended data object, the suspended object must first be loaded into main memory. In the event that there in not enough available main memory space to accommodate the needed object, one or more resident objects must be suspended.
Programs which provide object swapping between main memory and bulk memory employ a pointer in memory as a surrogate for each object. The pointer defines the physical address of its object. If the object is a code object, as opposed to a data object, the surrogate may include a short sequence of code which is generally known as a "stub vector". Entry to the code object is effected by execution of the stub vector code which assures that the object is resident or becomes resident. Code objects consist of code which is logically associated for ease of program execution. There may be several entry points to a single code object and each entry point has an associated entry stub vector.
Of necessity, all swapping systems slow program execution because of the delays incurred in suspending objects and restoring objects to resident status. The effectiveness of a swapping system is directly dependent on the quality of the decisions as to selection of objects to be suspended. Arbitrary selection of objects to be suspended tends to cause inconsistent and annoying delays in program execution. Some prior art swapping systems employ a "least recently used" (LRU) algorithm to select objects to be suspended. There are a number of different strategies for implementing an LRU process which operate with different degrees of success.
The selection of an object as a candidate to be suspended is not without risk. Care must be taken to insure that an object which is currently executing or an object which is directly or indirectly responsible for the currently executing object is not suspended without knowledge of how to resume execution of the suspended object.
While there are a number of prior art solutions to this problem, each solution has its own undesirable features. The following are a few of the known prior art solutions:
Wait until the program itself explicitly permits the code object to be suspended. Until that time, the code object must remain resident. This puts a heavy burden on the program designer.
Identify the current active object and trace all its antecedent objects which have not completed execution (usually because they have called upon each other in turn to do some part of the execution), and do not allow that set of objects to become suspended. While this is automatic and foolproof, some antecedent objects must remain resident, even though it may be a long time before their execution is resumed. Accordingly, there must be enough main memory to hold the largest possible chain of antecedents, which is generally much larger than an optimal size.
Require an object to return to its stub vector which has saved special information to enable safe return to its caller even if the caller needs to be made resident before return thereto. This allows a program to execute correctly; however, it has the drawback that both the entry and the return procedures are slowed by the need to log the calling information at the time of the call, and to unravel the information at the time of return. This solution is undesirably slow and the stub vectors are large.